import java.util.Random;

/**
 * Created by iss on 17/7/28.
 */
public class Test {


    public static int[] createArray(int length, int maxValue) {
        int[] ints = new int[length];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = new Random().nextInt(maxValue);
        }
        return ints;
    }


    //冒泡排序
    public static void popSlot(int[] ints) {
        int tmp;
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints.length - 1; j++) {
                //循环两次比较临近2数据
                if (ints[j] > ints[j + 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j + 1];
                    ints[j + 1] = tmp;
                }
            }
        }
    }

    //选择排序
    public static void selectSlot(int[] ints) {
        int s = 0;
        for (int i = 0; i < ints.length; i++) {
            s = ints[i];
            for (int j = i + 1; j < ints.length; j++) {
                //循环两次比较临近2数据
                if (ints[j] < s) {
                    ints[i] = ints[j];
                    ints[j] = s;
                    s = ints[i];
                }
            }
        }
    }

    //插入排序
    public static void insertSlot(int[] ints) {
        int i, j;
        int n = ints.length;
        int target;

        //假定第一个元素被放到了正确的位置上
        //这样，仅需遍历1 - n-1
        for (i = 1; i < n; i++) {
            j = i;
            target = ints[i];
            while (j > 0 && target < ints[j - 1]) {
                ints[j] = ints[j - 1];
                j--;
            }
            ints[j] = target;
        }
    }

    //基于理解写的插入排序 从数组的sub数组进行排序逐渐扩大
    public static void insertSlotByMe(int[] ints) {
        int tmp;
        for (int i = 1; i < ints.length; i++) {
            for (int j = i; j > 0; j--) {
                if (ints[j] < ints[j - 1]) {
                    tmp = ints[j];
                    ints[j] = ints[j - 1];
                    ints[j - 1] = tmp;
                }
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param arrays 需要排序的序列
     */
    public static void shellSort(int[] arrays) {
        if (arrays == null || arrays.length <= 1) {
            return;
        }
        //增量
        int incrementNum = arrays.length / 2;
        while (incrementNum >= 1) {
            for (int i = 0; i < arrays.length; i++) {
                //进行插入排序
                for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
                    if (arrays[j] > arrays[j + incrementNum]) {
                        int temple = arrays[j];
                        arrays[j] = arrays[j + incrementNum];
                        arrays[j + incrementNum] = temple;
                    }
                }
            }
            //设置新的增量
            incrementNum = incrementNum / 2;
        }
    }


    //划分
    public static void divide(int[] arr, int eleNum) {

        int leftPtr = 0, rightPtr = arr.length - 1;
        int middle = arr[eleNum];
        while (true) {
            while (leftPtr < rightPtr && arr[leftPtr] < middle) {
                leftPtr++;
            }
            while (rightPtr > -1 && arr[rightPtr] > middle) {
                rightPtr--;
            }

            if (leftPtr >= rightPtr) {
                // 已经划分完毕
                break;
            } else {
                // 交换
                int tmp = arr[leftPtr];
                arr[leftPtr] = arr[rightPtr];
                arr[rightPtr] = tmp;
            }
        }
    }

    //快速排序
    public static void quickSort(int arr[],int _left,int _right){
        int left = _left;
        int right = _right;
        int temp = 0;
        if(left <= right){   //待排序的元素至少有两个的情况
            temp = arr[left];  //待排序的第一个元素作为基准元素
            while(left != right){   //从左右两边交替扫描，直到left = right

                while(right > left && arr[right] >= temp)
                    right --;        //从右往左扫描，找到第一个比基准元素小的元素
                arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换

                while(left < right && arr[left] <= temp)
                    left ++;         //从左往右扫描，找到第一个比基准元素大的元素
                arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换

            }
            arr[right] = temp;    //基准元素归位
            quickSort(arr,_left,left-1);  //对基准元素左边的元素进行递归排序
            quickSort(arr, right+1,_right);  //对基准元素右边的进行递归排序
        }
    }


    //归并算法
    public static int[] merge(int[] ints1, int[] ints2) {
        int[] merge = new int[ints1.length + ints2.length];
        int i = 0;
        int j = 0;
        int count = 0;
        while (count < merge.length) {
            if (i == ints1.length) {
                merge[count] = ints2[j];
                j = j + 1;
                count++;
            } else if (j == ints2.length) {
                merge[count] = ints1[i];
                i = i + 1;
                count++;
            } else if (i < ints1.length && ints1[i] <= ints2[j]) {
                merge[count] = ints1[i];
                i = i + 1;
                count++;
            } else if (j < ints2.length && ints2[j] <= ints1[i]) {
                merge[count] = ints2[j];
                j = j + 1;
                count++;
            }
        }
        return merge;
    }

    //pos=1表示个位，pos=2表示十位
    public static int getNumInPos(int num, int pos) {
        int tmp = 1;
        for (int i = 0; i < pos - 1; i++) {
            tmp *= 10;
        }
        return (num / tmp) % 10;
    }


    //基数排序
    public static void radixSort(int[] a, int d) {

        int[][] array = new int[10][a.length + 1];
        for (int i = 0; i < 10; i++) {
            array[i][0] = 0;// array[i][0]记录第i行数据的个数
        }
        for (int pos = 1; pos <= d; pos++) {
            for (int i = 0; i < a.length; i++) {// 分配过程
                int row = getNumInPos(a[i], pos);
                int col = ++array[row][0];
                array[row][col] = a[i];
            }
            for (int row = 0, i = 0; row < 10; row++) {// 收集过程
                for (int col = 1; col <= array[row][0]; col++) {
                    a[i++] = array[row][col];
                }
                array[row][0] = 0;// 复位，下一个pos时还需使用
            }
        }
    }


    public static void findIndex(int[] ints, int target) {
        int l = 0;
        int r = ints.length - 1;
        find(ints, l, r, target);
    }


    public static void display(int[] ints) {
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + ",");
        }
        System.out.println();
    }

    //二分查找
    private static void find(int[] ints, int l, int r, int target) {
        int m = (l + r) % 2 == 0 ? (l + r) / 2 : (l + r) / 2 + 1;
        if (target == ints[m]) {
            System.out.println(m);
            return;
        } else if (l > r) {
            return;
        }
        //当目标值在数组左半区则r值变为m-1
        if (target < ints[m]) {
            int nr = m - 1;
            find(ints, l, nr, target);
        } else {
            int nl = m + 1;
            find(ints, nl, r, target);
        }
    }

    public static void main(String[] args) {
        int[] ints = createArray(10, 10000);
//        popSlot(ints);
//        display(ints);
//        ints = createArray(10, 10000);
//        selectSlot(ints);
//        display(ints);
//        ints = createArray(10, 10000);
//        insertSlot(ints);
//        display(ints);
//        ints = createArray(10, 10000);
//        insertSlotByMe(ints);
//        display(ints);
//        ints = createArray(10,10000);
        //       shellSort(ints);
        display(ints);
        //quickSort(ints,0,ints.length-1);
        radixSort(ints,10);
        display(ints);

//        int[] ints1 = createArray(10, 10000);
//        insertSlot(ints1);
//        int[] ints2 = createArray(10, 10000);
//        insertSlotByMe(ints2);
//        int[] ints3 = merge(ints1, ints2);
//        display(ints3);
    }
}